<!Doctype html>
<html>
<head>
    <script src="http://s1.bdstatic.com/r/www/cache/ecom/esl/1-8-8/esl.js"></script>
    
    <script src="http://ubilabs.github.io/kd-tree-javascript/kdTree.js"></script>

    <meta charset="utf-8">
</head>
<style>
    html, body {
        height: 100%;
        margin: 0px;
    }
</style>
<body>
    <canvas id="main"></canvas>
</body>
<script>
    require.config({
        packages: [{
            name: 'echarts',
            location: '../src',
            main: 'echarts'
        }, {
            name: 'zrender',
            location: '../../zrender/src',
            main: 'zrender'
        }]
    });

    require(['echarts/data/KDTree'], function (KDTree) {
        var points = [];
        var points2 = [];
        var width = window.innerWidth;
        var height = window.innerHeight;
        var canvas = document.getElementById('main');
        canvas.width = width;
        canvas.height = height;
        var ctx = canvas.getContext('2d');
        for (var i = 0; i < 50000; i++) {
            var point = [Math.round(width * Math.random()), Math.round(height * Math.random())];
            points.push({
                array: point
            });
            points2.push(point);
        }

        var time = performance.now();
        var kdTree1 = new KDTree(points);
        console.log(performance.now() - time);

        var squaredDistance = function (a, b) {
            a = a.array;
            b = b.array;
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
        }
        var squaredDistance2 = function (a, b) {
            return (a[0] - b[0]) * (a[0] - b[0]) + (a[1] - b[1]) * (a[1] - b[1]);
        }
        var kdTree2 = new kdTree(points2, squaredDistance2, [0, 1]);
        // Find nearest
        var p2 = [Math.round(width * Math.random()), Math.round(height * Math.random())];
        p = {
            array: p2
        };
        var time = performance.now();
        for (var i = 0; i < 50000; i++) {
            var nearest = kdTree1.nearest(p, squaredDistance);
        }
        console.log(performance.now() - time);
        console.log(p, nearest);

        // Find nearst N
        var nearestN = [];
        var time = performance.now();
        for (var i = 0; i < 50000; i++) {
            var nearest = kdTree1.nearestN(p, 5, squaredDistance, nearestN);
        }
        console.log(performance.now() - time);
        console.log(p.array, nearestN.map(function(a) {
            return a.array;
        }));

        setTimeout(function () {
            var time = performance.now();
            for (var i = 0; i < 50000; i++) {
                var nearest = kdTree2.nearest(p2, 5);
            }
            console.log(performance.now() - time);
            console.log(p2, nearest.map(function(a) {
                return a[0];
            }));
        }, 1000);

        // var buildSplitLines = function (node, minx, miny, maxx, maxy) {
        //     switch (node.axis) {
        //         case 0:
        //             var x = node.data[0];
        //             ctx.moveTo(x + 0.5, miny);
        //             ctx.lineTo(x + 0.5, maxy);
        //             ctx.stroke();
        //             node.left && buildSplitLines(node.left, minx, miny, node.data[0], maxy);
        //             node.right && buildSplitLines(node.right, node.data[0], miny, maxx, maxy);
        //             break;
        //         case 1:
        //             var y = node.data[1];
        //             ctx.moveTo(minx, y + 0.5);
        //             ctx.lineTo(maxx, y + 0.5);
        //             ctx.stroke();
        //             node.left && buildSplitLines(node.left, minx, miny, maxx, node.data[1]);
        //             node.right && buildSplitLines(node.right, minx, node.data[1], maxx, maxy);
        //             break;
        //     }

        // }
        // ctx.fillStyle = 'black';
        // buildSplitLines(kdTree1.root, 0, 0, width, height);

        // ctx.fillStyle = 'red';
        // for (var i = 0; i < points.length; i++) {
        //     var p = points[i];
        //     ctx.fillRect(p[0], p[1], 4, 4);
        // }
    })
</script>
</html>